# -*- coding: utf-8 -*-

"""869. 重新排序得到 2 的幂
给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。

示例 1：
输入：1
输出：true

示例 2：
输入：10
输出：false

示例 3：
输入：16
输出：true

示例 4：
输入：24
输出：false

示例 5：
输入：46
输出：true

提示：
1 <= N <= 10^9"""

class Solution:
    """考虑到N的限制在1~10^9，用 2 求幂枚举"""
    def reorderedPowerOf2(self, n: int) -> bool:
        if n == 10**9:
            return False

        ns = self.split_sort(n)
        minexp = self.place_exp_table[len(ns)]['min']
        maxexp = self.place_exp_table[len(ns)]['max']
        
        hopes = []
        for exp in range(minexp, maxexp+1):
            hopes.append(self.split_sort(2**exp))
        
        isok = False
        for hope in hopes:
            if ns == hope:
                isok = True
                break
        
        return isok

    def split_sort(self, n):
        ns = []
        while True:
            if n == 0:
                break
            t = n % 10
            ns.append(t)
            n = n // 10
        ns.sort()
        return ns
    
    place_exp_table = {
        1: {'min':0, 'max':3},
        2: {'min':4, 'max':6},
        3: {'min':7, 'max':9},
        4: {'min':10, 'max':13},
        5: {'min':14, 'max':16},
        6: {'min':17, 'max':19},
        7: {'min':20, 'max':23},
        8: {'min':24, 'max':26},
        9: {'min':27, 'max':29},
    }


if __name__ == '__main__':
    # for i in range(0, 31):
    #     print(i, 2**i)
    so = Solution()
    print(so.reorderedPowerOf2(8902300))
    print(so.reorderedPowerOf2(1))
    print(so.reorderedPowerOf2(10))
    print(so.reorderedPowerOf2(16))
